# 108. 发现环
# https://www.lanqiao.cn/problems/108/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/8
from collections import defaultdict


def get_cycle_nodes(n, edges):
    """
    找到图中环结构的所有节点
    :param n: 节点数量
    :param edges: 边的链接情况
    :return: 环中的节点
    """
    # 构建图的邻接表
    graph = defaultdict(list)
    for n1, n2 in edges:
        graph[n1].append(n2)
        graph[n2].append(n1)

    visited = [0] * (n + 1)  # 记录遍历情况, 其中0表示还未遍历, 1表示遍历中, 2表示已经遍历完成
    cycle_nodes = set()

    def dfs(path, node):
        """我写的dfs"""
        nonlocal cycle_nodes
        if visited[node] == 0:
            visited[node] = 1
            for i in range(len(graph[node])):
                if path[-1] == graph[node][i]:  # 如果是父节点则不访问, path[-1] 表示该节点的父节点
                    continue
                path.append(node)
                dfs(path, graph[node][i])
                path.pop()  # 此前这里没有进行回溯, 在部分情况下造成结果错误
            visited[node] = 2
        elif visited[node] == 1:  # 如果该节点处于正在遍历状态, 那么就是一个环
            idx = path.index(node)  # 通过path确定环中的节点, 如[0,1,2,3,4,2], 那么234就是环中的节点
            cycle_nodes.update(path[idx:])
        else:
            return

    def dfs_opt(path, node):
        """经过GPT修改后的, 看起来更加标准"""
        nonlocal cycle_nodes
        visited[node] = 1
        path.append(node)

        for neighbor in graph[node]:
            if neighbor == path[-2]:  # 跳过父节点
                continue
            if visited[neighbor] == 0:
                dfs(path, neighbor)
            elif visited[neighbor] == 1:  # 发现环
                idx = path.index(neighbor)
                cycle_nodes.update(path[idx:])  # 将环中的节点加入集合

        path.pop()
        visited[node] = 2

    dfs_opt([0], list(graph.keys())[0])

    # 处理为标准格式
    cycle_nodes = list(cycle_nodes)
    return " ".join(map(str, sorted(cycle_nodes)))


if __name__ == '__main__':
    # n = int(input())
    # inp = []
    # for i in range(n):
    #     inp.append(tuple(map(int, input().split())))
    # 测试用例1
    print(get_cycle_nodes(5, [(1, 2), (3, 1), (2, 4), (2, 5), (5, 3)]))  # 1 2 3 5

    # 测试用例2
    print(get_cycle_nodes(6, [(1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (4, 6), (5, 6)]))  # 2 3 4 5 6

    # 测试用例3
    print(get_cycle_nodes(6, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (4, 6)]))  # 4 5 6

    # 测试用例4
    inp = []
    with open("../data/108.in", "r") as file:
        n = int(file.readline())
        for i in range(n):
            inp.append(tuple(map(int, file.readline().split())))
    print(get_cycle_nodes(n, inp))  # 1 3 60 96 97
